package fhq.hcmute.qrcode.reedsolomon;

import fhq.hcmute.qrcode.util.QRCodeException;
import static fhq.hcmute.qrcode.util.QRCodeException.*;

/**
 * @author Hien Nguyen Le
 * @Email: nglehien@gmail.com
 */
public class ReedSolomon {

	/**
	 * @Step 1: Create Message Polynomial.
	 * @Step 2: Create Generator Polynomial.
	 * @Step 3: We will divide the message polynomial by the generator
	 *       polynomial. The remainders of the division are error correction
	 *       code words.
	 * @return Error Correction Code Words.
	 * @throws QRCodeException
	 */
	public int[] encode(int[] dataCodewords, int errorCorrectionCodewords)
			throws QRCodeException {
		int exponent = dataCodewords.length + errorCorrectionCodewords - 1;
		Polynomial messagePolynomial = createMessagePolynomial(dataCodewords,
				exponent);
		Polynomial generatorPolynomial = createGeneratorPolynomial(
				errorCorrectionCodewords, dataCodewords, exponent);
		messagePolynomial.devide(generatorPolynomial);
		return messagePolynomial.getRemainder().getArrayCoefficient();
	}

	public int[] decode(int[] dataCodewords, int nSyndrome)
			throws QRCodeException {
		Polynomial receivedPolynomial = Polynomial.createPolynomial(
				dataCodewords, dataCodewords.length - 1);
		int[] syndromes = new int[nSyndrome];
		boolean hasError = false;
		for (int i = 0; i < nSyndrome; i++) {
			int x = GaloisFiled256.getExp(i);
			int value = receivedPolynomial.evaluateAt(x);
			syndromes[nSyndrome - i - 1] = value;
			if (value != 0) {
				hasError = true;
			}
		}
		if (hasError) {
			Polynomial syndromePolynomial = createMessagePolynomial(syndromes,
					syndromes.length - 1);
			EuclideanResult euclideanResult = euclideanAlgorithm(
					new Polynomial(new Monomial(1, nSyndrome)),
					syndromePolynomial, nSyndrome);
			Polynomial errorLoca = euclideanResult.getErrorLocation();
			Polynomial errorEval = euclideanResult.getErrorEvaluation();
			int[] errorLocations = findErrorLocations(errorLoca);
			int[] errorMagnitudes = findErrorMagnitudes(errorEval,
					errorLocations);
			correctCodeword(errorMagnitudes, errorLocations,
					dataCodewords);
			return dataCodewords;
		}
		return null;
	}

	/**
	 * Correct the error by adding the complement of the error size value to
	 * each error position. Note: Error position = Length of error Locations
	 * array subtract with Log of error location.
	 * 
	 * @param errorMagnitudes
	 * @param errorLocations
	 * @param dataCodewords
	 * @throws QRCodeException
	 */
	private void correctCodeword(int[] errorMagnitudes, int[] errorLocations,
			int[] dataCodewords) throws QRCodeException {
		for (int i = 0; i < errorLocations.length; i++) {
			int errorPosition = dataCodewords.length - 1
					- GaloisFiled256.getLog(errorLocations[i]);
			if (errorPosition < 0) {
				throw new QRCodeException(QR_CODE_NOT_FOUND);
			}
			dataCodewords[errorPosition] = dataCodewords[errorPosition]
					^ errorMagnitudes[i];
		}
	}

	private int[] findErrorLocations(Polynomial errorLocation)
			throws QRCodeException {
		int numberError = errorLocation.getMaxExponent();
		int[] result = new int[numberError];
		int count = 0;
		for (int i = 0; i < 256; i++) {
			if (errorLocation.evaluateAt(i) == 0) {
				result[count++] = GaloisFiled256.inverse(i);
			}
		}
		return result;
	}

	private int[] findErrorMagnitudes(Polynomial errorEvaluation,
			int[] errorLocations) throws QRCodeException {
		int s = errorLocations.length;
		int[] result = new int[s];
		for (int i = 0; i < s; i++) {
			int xInverse = GaloisFiled256.inverse(errorLocations[i]);
			int temp = 1;
			for (int j = 0; j < s; j++) {
				if (j != i) {
					temp = GaloisFiled256.multiply(temp, 1 ^ GaloisFiled256
							.multiply(errorLocations[j], xInverse));

				}
			}
			result[i] = GaloisFiled256.multiply(
					errorEvaluation.evaluateAt(xInverse),
					GaloisFiled256.inverse(temp));
		}
		return result;
	}

	/**
	 * SEE MORE:
	 * <a>http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction
	 * #Euclidean_decoder</a>
	 * 
	 * @param s
	 *            : syndrome polynomial
	 * @param t
	 *            : number of syndrome
	 * @param r
	 *            : X^t
	 * 
	 * @return sigma and omega Polynomial
	 * @throws QRCodeException
	 */
	private EuclideanResult euclideanAlgorithm(Polynomial r, Polynomial s, int t)
			throws QRCodeException {
		if (r.getMaxExponent() < s.getMaxExponent()) {
			Polynomial temp = r;
			r = s;
			s = temp;
		}
		Polynomial a = new Polynomial(new Monomial(1, 0));
		Polynomial aLast = new Polynomial();
		Polynomial b = new Polynomial(new Monomial(0, 0));
		Polynomial bLast = new Polynomial();
		Polynomial sLast = s;
		while (s.getMaxExponent() >= t / 2) {
			Polynomial q = new Polynomial();
			r.devide(s);
			q = r.getQuotient();// Q=R[i]/S[i]
			s = r.getRemainder();// S[i+1]
			r = sLast;// R=S[i]
			sLast = s;
			aLast = a;
			bLast = b;
			q.multiply(aLast);
			q.add(bLast);
			a = q;
			b = aLast;

		}
		int inverse = GaloisFiled256.inverse(a.getCoefficientByExponent(0));
		Polynomial errorLocation = a.multiply(inverse, 0);
		Polynomial errorEvalation = s.multiply(inverse, 0);
		EuclideanResult result = new EuclideanResult(errorLocation,
				errorEvalation);
		return result;
	}

	/**
	 * 
	 * @param int[] integerValues
	 * @param exponentFirstTerm
	 * @return Polynomial of Message
	 * @throws QRCodeException
	 */
	private Polynomial createMessagePolynomial(int[] integerValues,
			int exponentFirstTerm) throws QRCodeException {
		return Polynomial.createPolynomial(integerValues, exponentFirstTerm);
	}

	/**
	 * We create the generator Polynomial. we will divide the message Polynomial
	 * by the generator polynomial to create our error correction code words.
	 * 
	 * @return
	 * @throws QRCodeException
	 */
	private Polynomial createGeneratorPolynomial(int eccCodewords,
			int[] integerValues, int exponentFirstTerm) throws QRCodeException {
		Polynomial defaultPolynomial = new Polynomial();
		defaultPolynomial.add(new Monomial(1, 1));
		defaultPolynomial.add(new Monomial(1, 0));

		for (int i = 0; i < eccCodewords - 1; i++) {
			Polynomial multiplyPolynomial = new Polynomial();
			multiplyPolynomial.add(new Monomial(1, 1));
			multiplyPolynomial
					.add(new Monomial(GaloisFiled256.getExp(i + 1), 0));
			defaultPolynomial.multiply(multiplyPolynomial);
		}
		return defaultPolynomial;
	}

	private class EuclideanResult {
		Polynomial errorLocation;
		Polynomial errorEvaluation;

		public EuclideanResult(Polynomial errorLocation,
				Polynomial errorEvaluation) {
			this.errorLocation = errorLocation;
			this.errorEvaluation = errorEvaluation;
		}

		public Polynomial getErrorLocation() {
			return errorLocation;
		}

		public Polynomial getErrorEvaluation() {
			return errorEvaluation;
		}

	}
}
